<?php
/**
 * User: LRZ
 * Date: 2020/2/27
 * Time: 16:02
 */
$array     = [95, 94, 91, 98, 99, 90, 99, 93, 91, 92, 99];
$sortArray = countingSort($array);
print_r($sortArray);

function countingSort($array)
{
    /*
     *  计数排序实现思路：
     *    1. 得到数组的最大值和最小值，并算出差值d
     *    2. 创建统计数组，并统计对应元素的个数
     *    3. 统计数组做变形，后面的元素等于前面的元素之和
     *    4. 倒序遍历原始数组，从统计数组找到正确位置，并输出到结果数组
     */

    // 算出最大最小值和差值
    $max = max($array);
    $min = min($array);
    $d   = $max - $min;

    // 创建统计数组，并统计元素个数
    $countArray = array_fill(0, $d + 1, 0);
    foreach ($array as $iValue) {
        $countArray[$iValue - $min]++;
    }

    // 统计数组变形
    for ($i = 1, $iMax = count($countArray); $i < $iMax; $i++) {
        $countArray[$i] += $countArray[$i - 1];
    }

    // 倒序遍历原始数组，从统计数组找到正确位置，并输出到结果数组
    $length      = count($array);
    $sortedArray = array_fill(0, $length, 0);
    for ($i = $length - 1; $i >= 0; $i--) {
        $sortedArray[$countArray[$array[$i] - $min] - 1] = $array[$i];
        $countArray[$array[$i] - $min]--;
    }
    return $sortedArray;
}